1. Field of the Invention
The present invention relates to the field of caching data program instructions for use by a microprocessor. More specifically, the present invention relates to the art of predicting and prefetching cache lines likely to be required by the microprocessor based on prior fetching history.
2. Description of the Related Art
As general purpose processors are getting faster, the speed gap between the microprocessor and the main memory system increases. While the speed of microprocessors generally increases by a factor of 2 every 18 months, DRAM speed improves by only about 5% per year. Moreover, since the DRAM based main memory system is external to the microprocessor, considerable delay is incurred from the time the microprocessor asks for data from memory until the microprocessor receives the first piece of that information so it can continue computing. One technique that helps overcome this latency problem is cache memory. Cache memories are fast memory buffers that store blocks of data and instructions that were recently used by the microprocessor. As microprocessors get faster, they execute larger programs with larger data sets. For large programs with large data sets, caches may be ineffective. That is, large programs executing on computers with large caches could still suffer a large number of cache misses.
Prefetching is a known technique by which the processor anticipates future data accesses and brings the data from memory into a fast buffer before the executing program references the data. If a large portion of the prefetch data is actually used, considerable improvement in performance may be realized due to the decrease in the average memory access time. Known prefetching techniques such as stride calculation and stream buffering may perform adequately for detecting memory accesses at a fixed stride or a combination of a few simultaneous memory access strides, but they perform poorly in situations where the access has a repeating complex memory access pattern. For example, if an application program repeatedly accesses sets of records in a linked list, previous prefetching techniques will not identify the complex access pattern, and the prefetching will not be effective.
The present invention is directed to overcoming, or at least reducing the effects of, one or more of the problems set forth above by providing a prefetching technique capable of identifying complex patterns in memory accesses.